package Sort

func BulletSort(arr []int) []int {
	// 冒泡排序
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}

func SelectSort(arr []int) []int {
	// 选择排序 - 找比第i个还要小的数，找到就交换
	for i := 0; i < len(arr)-1; i++ {
		min, pos := arr[i], i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < min {
				min, pos = arr[j], j
			}
		}
		if pos != i {
			arr[i], arr[pos] = arr[pos], arr[i]
		}
	}
	return arr
}

func InsertSort(arr []int) []int {
	// 插入排序 - 将第i个插入前面i-1个有序序列中
	for i := 1; i < len(arr); i++ {
		// 因为序列往后挪会覆盖arr[i]，所以需要保存arr[i]
		tmp, j := arr[i], i
		if arr[i-1] > tmp {
			// 如果有序序列最后一个比arr[i]大，就需要将有序序列挪出位置给arr[i]
			for ; j > 0 && arr[j-1] > tmp; j-- {
				arr[j] = arr[j-1]
			}
		}
		arr[j] = tmp
	}
	return arr
}

func MergeSort(arr []int) []int {
	/*
		归并排序
		利用递归与分治技术将数据序列划分成为越来越小的半子表
		先对半子表进行排序，再用递归的方法将完成排序的半子表合并成越来越大的有序序列
	*/
	mergeFunc := func(left, right []int) (res []int) {
		// 合并函数 - 迭代左右两个子序列，将小的值追加到结果中
		l, r := 0, 0
		for l < len(left) && r < len(right) {
			if left[l] < right[r] {
				res = append(res, left[l])
				l++
			} else {
				res = append(res, right[r])
				r++
			}

		}
		// 将剩下的有序子序列追加到结果中
		res = append(res, left[l:]...)
		res = append(res, right[r:]...)
		return
	}
	// 递归跳出条件
	if len(arr) <= 1 {
		return arr
	}
	// 将序列分成半子表
	midPos := len(arr) / 2
	left := MergeSort(arr[:midPos])
	right := MergeSort(arr[midPos:])
	// 合并
	return mergeFunc(left, right)
}

func QuickSort(arr []int) []int {
	/*
		快速排序
		主要是利用递归，先找到基准值，迭代元素，小于基准值的作为左边子序列，大于基准值的作为右边子序列
		递归左右子序列，直到子序列元素数量小于等于2个
		注：归并排序和快速排序区别
		归并排序是将无序序列半边元素作为分组，快速排序是根据无序序列某一项的值作为基准将元素分组
		归并排序需要对两个有序子序列进行迭代合并，快速排序只需要将两个子序列合并起来
	*/
	var quickSort func(arr []int, left, right int)
	quickSort = func(arr []int, left, right int) {
		if left >= right {
			return
		}
		l, r := left, right
		pivot := arr[l]
		for l < r {
			// 判断l是否小于r，如果l大于等于r就说明元素已经成功分配到左右序列
			for l < r && arr[r] >= pivot {
				// 从后往前扫描，如果有元素小于基准值则将r指向该元素
				r--
			}
			if l < r {
				// 如果这时候l还比r小，就说明右边有元素小于基准值，将该元素替换l的位置，然后将l加一，此时右边出现空位
				arr[l] = arr[r]
				l++
			}
			for l < r && arr[l] < pivot {
				//  从前往后扫描，如果有元素大于基准值，则将l指向该元素
				l++
			}
			if l < r {
				// 把大于基准值的元素写回去刚刚出现的空位
				arr[r] = arr[l]
				r--
			}
		}
		// 最后l和r会相遇，相遇的位置就是基准值的位置
		arr[l] = pivot
		// 递归调用该方法 - 空出l的原因是因为l是基准值的位置，肯定是已经序列的中位数
		quickSort(arr, left, l-1)
		quickSort(arr, l+1, right)
	}
	quickSort(arr, 0, len(arr)-1)
	return arr
}

func ShellSort(arr []int) []int {
	/*
		希尔排序
		将无序序列分成多个子序列（数量较少），然后对每个子序列进行直接插入排序
		等到无序序列变得基本有序（步长因子等于1的情况）之后，再对所有的元素进行一次直接的插入排序
		子序列长度：步长因子 子序列：步长序列
		主要利用插入排序在近乎有序的序列中排序性能较优的特点，因为插入排序有提前终止的性质（找到坑就插进去）
		通过跳跃式移动，使排序的效率提高
	*/
	for step := len(arr) / 2; step > 0; step /= 2 {
		// 计算步长因子
		for i := step; i < len(arr); i++ {
			// 进行插入排序
			tmp, j := arr[i], i-step
			for ; j >= 0 && arr[j] > tmp; j -= step {
				arr[j+step] = arr[j]
			}
			arr[j+step] = tmp
		}
	}
	return arr
}

func MaxHeapSort(arr []int) []int {
	/*
		最大堆排序 - 特殊的树形数据结构，通常都是完全二叉树（叶子节点都比根节点小或大）
		同时根节点两个子树也分别是一个堆
		注：二叉树第i个节点的父节点是(i-1)/2，左叶子节点2i+1，右叶子节点2i+2
		排序步骤：
		1. 初始把序列当作一个顺序存储的二叉树，然后调整其为一个大顶堆
		2. 将堆的最后一个元素与堆顶元素进行交换，堆的最后一个元素即为最大元素
		3. 接着将前(n-1)个元素重新调整为一个大顶堆，再将堆顶元素与当前堆最后一个元素进行交换获得次大的记录
		4. 重复上述过程，直到堆中只有一个元素为止，该元素即为最小记录

		一共两个过程：构建堆、交换堆顶元素与最后一个元素的位置
	*/
	var heapify func(arr []int, pos int)
	heapify = func(arr []int, pos int) {
		// arr指需要构建堆的序列，pos指需要对哪个节点构建堆

		if pos > len(arr) {
			// 递归条件，构建堆的目标节点必须小于切片长度
			return
		}
		// 叶子节点计算公式
		c1 := (2 * pos) + 1
		c2 := (2 * pos) + 2
		max := pos
		// 判断两个叶子节点是否大于需要构建堆的节点，如果是则将叶子节点作为根节点
		if c1 < len(arr) && arr[c1] > arr[max] {
			max = c1
		}
		if c2 < len(arr) && arr[c2] > arr[max] {
			max = c2
		}
		// 如果需要构建堆的节点不是最大节点，则交换最大节点和目标节点
		if max != pos {
			arr[pos], arr[max] = arr[max], arr[pos]
			// 用刚刚交换的叶子节点构建堆
			heapify(arr, max)
		}

	}
	// 将所有子树调整成堆就能将整个序列调整成堆 - 根据(i-1)/2获取最后一个子树父节点位置
	for i := ((len(arr) - 1) - 1) / 2; i >= 0; i-- {
		heapify(arr, i)
	}
	for i := len(arr) - 1; i >= 0; i-- {
		// 将根节点和最后一个元素进行交换
		arr[0], arr[i] = arr[i], arr[0]
		// 砍断最后一个节点，然后用刚刚交换的第一个节点构建堆
		heapify(arr[:i], 0)
	}
	return arr
}

func MinHeapSort(arr []int) []int {
	/*
		最小堆排序
	*/
	var heapify func(arr []int, pos int)
	heapify = func(arr []int, pos int) {
		// arr指需要构建堆的序列，pos指需要对哪个节点构建堆

		if pos > len(arr) {
			// 递归条件，构建堆的目标节点必须小于切片长度
			return
		}
		// 叶子节点计算公式
		c1 := (2 * pos) + 1
		c2 := (2 * pos) + 2
		min := pos
		// 判断两个叶子节点是否小于需要构建堆的节点，如果是则将叶子节点作为根节点
		if c1 < len(arr) && arr[c1] < arr[min] {
			min = c1
		}
		if c2 < len(arr) && arr[c2] < arr[min] {
			min = c2
		}
		// 如果需要构建堆的节点不是最小节点，则交换最小节点和目标节点
		if min != pos {
			arr[pos], arr[min] = arr[min], arr[pos]
			// 用刚刚交换的叶子节点构建堆
			heapify(arr, min)
		}

	}
	// 将所有子树调整成堆就能将整个序列调整成堆 - 根据(i-1)/2获取最后一个子树父节点位置
	for i := ((len(arr) - 1) - 1) / 2; i >= 0; i-- {
		heapify(arr, i)
	}
	for i := len(arr) - 1; i >= 0; i-- {
		// 将根节点和最后一个元素进行交换
		arr[0], arr[i] = arr[i], arr[0]
		// 砍断最后一个节点，然后用刚刚交换的第一个节点构建堆
		heapify(arr[:i], 0)
	}
	return arr
}
